package find.longest.substring;

import java.util.HashMap;
import java.util.Map;

/**
 * @Time 2020/1/2
 * @author 王光浩
 * @Need 给出一个字符串，获得其中最长但不包含重复字符的字符串的长度。
 * @Thinking 使用HashMap。HashMap的key值为字符，value为对应的下标。
 * 			 思路：将字符串中的字符加入到HashMap中，如果出现待加入字符出现在HashMap中则获取其中
 * 			            对应的value，将value+1作为下一次循环的下标，并计算当前HashMap的大小与当前符合
 *                要求最长长度进行比较，如果大于则更改最长度，然后将HashMap清空。（循环结束的条件是
 *                i==字符串长度）
 *           复杂度：时间复杂度O（n^2），空间复杂度O（n）。
 *           不足：在计算最长字符串的时候对于重复的元素反复遍历。
 */
public class MyMethodOne {
    public int lengthOfLongestSubstring(String s) {
        Map<Character,Integer> longestSub=new HashMap<Character,Integer>();
        int maxLen;
        int len;
        int i=0;                 //当前字符所在位置
        maxLen=len=s.length();
        //找出最大长度
        while(i<len) {
        	if(!longestSub.containsKey(s.charAt(i))) 
        		longestSub.put(s.charAt(i), i);
        	else {
        		i=longestSub.get(s.charAt(i));  //重新定位i
        		maxLen=(maxLen>=longestSub.size()?maxLen:longestSub.size());  //找出最长的子字符串
        		longestSub.clear();
        	}
        	i++;
        }
        maxLen=(maxLen>=longestSub.size()?maxLen:longestSub.size());
        return maxLen;
    }
}
